package com.mzy.linear_struct.hot100.双指针;

import com.sun.jmx.remote.internal.ArrayQueue;
import kotlin.StandardKt;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @Author: mizy3
 * @Date: 2024/08/11/下午5:04
 * @Description:
 */
public class Pro42接雨水 {

    private int trap(int[] height) {
        Deque<Integer> stack = new LinkedList<>();

        int ans = 0;
        stack.push(0);

        for (int i = 1; i < height.length; i++) {
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                Integer mid = stack.pop();
                if (!stack.isEmpty()) {
                    // i 为right
                    Integer left = stack.peek();
                    int h = Math.min(height[left], height[i]) - height[mid];
                    int w = i - left - 1;
                    int hold = h * w > 0 ? h * w : 0;
                    ans += hold;
                }
            }
            stack.push(i);
        }

        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Pro42接雨水().trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
    }


}




















